package com.mzy.linear_struct.ks.动规;

/**
 * @Author: mizy3
 * @Date: 2024/08/22/上午10:09
 * @Description:
 */
public class 乘积最大子数组 {
    public int maxProduct(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0]; // [i][0]表示连续子数组的最小乘积
        dp[0][1] = nums[0]; // [i][1]表示连续子数组的最大乘积
        int max = nums[0];

        // Math.max(dp[i - 1][1] * nums[i], nums[i]);
        // [2,3,-2,4]
        for (int i = 1; i < dp.length; i++) {
            if (nums[i] >= 0) {
                dp[i][0] = Math.min(dp[i - 1][0] * nums[i], nums[i]);
                dp[i][1] = Math.max(dp[i - 1][1] * nums[i], nums[i]);
            } else {
                dp[i][0] = Math.min(dp[i - 1][1] * nums[i], nums[i]);
                dp[i][1] = Math.max(dp[i - 1][0] * nums[i], nums[i]);
            }
            max = Math.max(max, dp[i][1]);
        }
        return max;
    }


    public static void main(String[] args) {
        new 乘积最大子数组().maxProduct(new int[]{2, 3, -2, 4});
    }
}
























